Naruto Uzumaki Uchiha Shinobi Of The Mist
by Connor16
Summary: A what if story. Instead of the leaf being the first village. Madara allies with the Uzumaki Clan to form the Hidden Mist Village making it the strongest village in the Elemental Nations due to them being a more battle hardened village.
1. Chapter 1

The dream of Madara Uchihaand Hashirama Senju remained just that a dream. At least for the time being. When the two meet at the river both of their clans were at war with each other. A war that the two young shinobi believed was pointless, what  
with all the meaningless deaths or clansmen and younger brothers. Nevertheless it was this very war that brought the brothers in all but friend together.

Both had dreams of changing the world for the better. A dream that would bring the end of war and countless deaths. A dream that ensured the young children got to grow up safe and sound, instead in times of war. Yes a simple dream that would remain that  
a dream.

The Uchiha and Senju were two of the top three strongest clans in the war. Which was why they were at war. Both clan heads wanting to prove the strength of their respective clans. Just when most members of both clans including the outside world, werestarting  
to wonder when the stupid war would end. The Uchiha clan got hired by one of the Daimyos to deal with the Kagyua clan. The current head of the war band clan was on a bloody rampage, he was attacking clans left and right offering no quarter. Finally  
having enough the Daimyo of the land hired them to put them in their place, and kill the leader. Not one to turn down a request, Madara's father packed up the clan and went to war with theKagyua. A war that would force the brothers apart and  
last for some time.

* * *

 _(3 Years Later)_  
 _  
_

Three years have past since the Uchiha's and Kagyua went to war. Three long years since Madara last seen his best friend. He was starting to wonder why he kept on fighting. Sixteen years old and he felt like he was ninety. But he kept on pushing forward  
so he could make his dream a reality. He was currently in his room resting before the mission. It was a four man black ops job. They were to sneak in kill the guards, lower their defenses and open the gate to allow the main force inside. The main...sorry  
the second main reason for the war lasting these past few years, was because the Kagyua encampment were on the high ground. Giving them the perfect defense. If they could get their forces through the gate, they could kill the clan head Sinbon, force  
the clan to surrender and form a peace treaty. Madara had a chance to end this war with few bloodshed, he wasn't going to let this chance slip through.

* * *

 _(Night)_  
 _  
_

It was finally night time and Madara was dressed in red armor along with three other clansman. Under the cover of darkness they swiftly moved to the insertionpoint. Once their they check to make sure the coast was clear before scaling the wall.

"Alright you all know you orders. Two of you secure the gate and be ready to open. We'll take care of the guard post. Move out!" He ordered before they all moved to their positions.

With his Sharingan active he pulled out few kunai knives before throwing them at their respective targets. Moving forward he jumpedup onto a watch tower giving the guard a chop to the neck. He then dropped down on top of another guard knocking,  
roundhouse kicking another knocking them out. Pulling out a knife he quickly deflected another thrown at, and engaged the prepatraitor in combat. Dodging and knocking away the attacks, Madara got inside their guard punching him in stomach getting  
them to fall before kneeing them in the face. Giving the signal that his job was clear and to open the gates. His mission was completed and end a three year war in a night. He just hoped his father would keep his word.

* * *

 _(Uchiha Compound)_  
 _  
_

"What the hell do you mean, you won't let them?! They surrendered father, there's no need to treat them like animals. We should offer to form an alliance!" Madara yells at his father. He was frustrated with the man. His father had just finished telling  
him that he was going to turn the females into breeding mules, because he wouldn't let their crimes against the Damiyo and their clan go unpunished.

"It's exactly as I already told you. That clan is full of nothing but blood crazed savages. They committed crimes that they must be punished for. Their females will be of great use to our man." His father says not even looking at him.

"But the next clan head is a women." He protects. Getting a grunt of agreement from his father.

"Yes I've noticed, and she's quite beautiful as well. She will be an excellent women to bare me strong sons to replace the ones I've lost."

That did it. His father saw his dead brothers as nothing more than tools, that could be replaced. He loved his siblings dearly, it's why he kept getting stronger to protect his baby brother Izuna. He lost all his brothers because of this man, his mother  
died from the heartache of losing her children. In that moment he had enough of this man. It was time for a new head of the clan. His Sharingan activated and spinning violently, he charged at his father.

* * *

 _(Next Day)_  
 _  
_

"Lady Maya. I can't tell you how much of an honor it is to form this alliance with your clan." Madara said respectively holding out his hand to shake. He was wearing a high collard blue shirt with the clan crest on the back, and blue pants with black  
sandals. Maya was wearing a white kimono dress with a rose petal design. She was a beautiful warrior type women, white hair tied in a ponytail, pale white skin, bright green eyes and hourglass figure, medium size chest and long shapely legs.

"The pleasure is all mine Lord Uchiha. If I may asked, where is your father?" She asked curiously taking his hand.

Already expecting such a question Madara only smiled answering. "My father unfortunately suffered a terrible accident last. Therefore promoting me as the next head."

"I'm sorry for your lost. However I get the feeling things will be much better under your leadership." Giving her condolences.

She had no idea.

* * *

 _(8 Years Later)_  
 _  
_

Eight years have passed since the alliance between both the Uchiha and Kagyua clans was made. True to her word Madara made some changes to his clan. Firstly he had finally called an end to war with his and the he made quite known  
that his clan would only enter a war to stop it, not to prove how strong they were.

Now here we are with a twenty four year old Madara laying in the grass, with his sister figure Maya. After becoming heads of their respective clans, the two word closely together. Outsiders would think they were a thing but they weren't. When they were  
younger all they felt was a physical sexual attraction, and trusted each other with losing their virginities instead of to some stranger. Besides that they found they had the same goals and ideals. So here they were relaxing in the grass.

"I still think you should make this dream of yours happen Madara." Maya says again.

He had told her of both his and Hashirama's dream of creating a village so that young ones would have a place to grow up safety. One that she whole heartily agreed with and kept trying to get him to do it.

"Once again I'll say how? We're only two clans Maya. No one is going to take us seriously. Hell they still don't take us seriously. The world still believes that the Kagyua are war crazed savages, and the Uchiha still power hungry. No matter what we did  
it didn't matter." He groans.

"It matters to our clans. With the work the two of have done since forming our alliance, they're truly happy. For the first time in their lives. My clan feel like they can freely choose who they can be. And I know yours feel the same. You say that the  
rest of the world won't see our way, then make them see it. The Uchiha and Senju are two of the strongest clans in the world. What's the third?The one that is practically the voice of reason in this fucked up world."

"The Uzumaki's." Madara muttereds getting a nod of agreement from her.

"Madara you and Hashirama are considered gods of our life time, giving you the power to change the world. Only question is will you use it?"

* * *

 _(Whirlpool, Uzumaki compound)_  
 _  
_

Madara made the self journey all the way to Whirlpool. He was going to speak to the clan head Mito Uzumaki and hopefully forge an alliance. He was excited and nervous. Excited because he was taking the first step to make his deem true, nervous because  
there was a chance he would be turned down, but also because he was meeting Mito who was the love of his life. Even when they were children he considered her beautiful and that beauty only grew with age.

"Lord Uchiha. Lady Mito will see you now." One of the guards inform him breaking him out of his musing. Thanking the guard he walks inside the main chamber where at the end sat Mito. Just the sight of her caused his breath to hitch and heart to skip a  
few beats. Her long Crimson hair tied into twin buns, fair white skin that seemed to be glowing, dark blue eyes that were locked on to him, thin red lips, large chest compressed tight against her dress, long Shaply toned legs crossed over the over,  
and he could only that she had a nice tight butt.

"Madara this is quite anunexpected visit. I must admit I was surprised that you wanted to speak with me."

"Lady Uzumaki. May I say that your beauty is quite unlike any I've ever laid eyes apon. I have come in hopes of forming an alliance." He says bowing respectfully.

"An alliance? And why would you want that? From what I've heard your alliance with Kagyua clan has been beneficial for you both. Or do you hope to gain another strong ally to attack the Senju clan?"

"As you may have heard lady Uzumaki. I've put an end to that war not long after becoming head of the clan."

"Yes I've heard, and I'm sure you've heard that there's other clans in the world believing it to be farce."

"Let them think what they wish milady. I will not let that stop me from mission."

"Oh? And what mission would that be?" She asked curiously.

"World peace milady. A world where there is no war, and children can grow up in a safe environment with the threat of war round the corner." He answered truthfully surprising her. "I've come to you today in hopes that you'll help me achieve that dream.  
With the backing of the Uzumaki clan others would no doubt join."

After hearing what it was he was after. Mito would be lying if she wasn't intrigued by this, but she needed to one more thing before giving her answer. "Do you truly believe that such a feat can be accomplished?"

Looking up into her eyes with afiery determination burning in his he nodded. "I truly do milady, but only if we all work together toward that future can it truly happen." He answered leaving them in a moment of silence.

"A simple alliance will not be enough to get this dream off the ground." Mito finally spoke almost dashing the Uchiha hope, until she continued. "If you want others to follow you Madara, a simple alliance between our clans will not suffice. The other  
clans most know how serious you are about this."

"Then what do you propose milady." He said respectively.

"A political marriage between us." She answered shocking him to the core. "Marriage between two powerful clans will show the world just how serious we are. It will show them that we mean business. Do you accept this proposition?"

Still shocked at the proposal all he could do was nod his head with a slight blush. Getting a smile from her. "Good our wedding will take place as soon as possible."

* * *

 _(Wedding)_

He couldn't believe it. He literally couldn't believe that he was now married to the love of his life. It was honestly the best day of his life that he couldn't get rid of the stupid smile on his face.

"Tell me dear husband. Have you come up with a name for this safe haven we'll build." Mito asked her husband getting a nod.

"I was thinking about calling itthe Hidden Mist Village." 


	2. Chapter 2

News of the union between the Uzumaki and Uchiha's spread like wild fire. Suddenly all the clans and Daimyowere forced to take the war clan seriously. In fear of their new power, they not only had the Kaguya clan whose bodies were literally a weapon,  
but the Uzumaki clan as well who were known for their long lifespan but seal masters as well. They were now the biggest threat to the in the world having all the power. Only one not threatened was the Daimyo of Water Country, because to him it meant more  
protection for his section of the land. So when Madara came before him letting him know that three clans were forming a village, he didn't hesitate giving his support.

Pretty soon the other clans in the land wanted to join in, knowing that the smartest decision was to ally with the people who now had the most power.

Madara was ecstatic about the whole thing. After his marriage with Mito, they proceeded with creating their village on a large island, with smaller ones all around itthat was connected to the main land by a huge bridge, or sailing by sea. Not long  
after getting settled on the island, andmoving all three clans to their new compounds. Other clans such as the Yuki, Hōzuki, Terumi and Gyokame joined them as well. Officially being named the first village in the Elemental Nations.

Not wanting to be left behind in face of this new power, other clans startedcoming together forming villages themselves. In the lands of Lightning, Wind, Earth and Fire. However the only village that he truly cared about was the Hidden Leaf created  
by the Senju and Hyuuga clan. Even if it wasn't something they started together, Madara was happy that they were still achieving their dreams.

Currently he was walking the streets of Kirigakure, admiring all the shops thatwere starting to open for the day. Kirigakure was a beautiful village surrounded by mist obviously, but with green vegetation that onlygrew by the sea, light brown cylinder  
buildings with plants that were growing on the rooftop. Surrounded by mountain tops and a large forest perfect for teaching the childrensurvival training.

It was a huge change from from seeing people with hardened faces, to both civilians and shinobi with carefree smiles talking like no tomorrow.

"I can't believe it's finally happened." He mutters to himself smiling slightly.

"Well believe it." He hears a voice behind him, turning to see his younger brother.

"Izuna. When did get back?" Madara asked not knowing what to say. Truth of the matter was that therewas a riftbetween the two brothers, that started to form after the alliance with Maya's clan and it only got worse after his marriage with  
Mito. Not wanting to stay in the peaceful village for more than a few weeks, or if lucky a month. Izuna had taken to traveling the nation in stead. That and his opinion would always put the two at odds. Izuna believed that with the power they had  
at their disposal, they should use itto wage war on the other villages. However Madara would have none of it, he made a promise that the younger generation would live rich full lives.

"I just got back. Thought I should let you know what the other nations are up to." Izuna glares at his brother after Madara groans rolling his eyes.

"We'll talk about this in the main building." Madara said not wanting to argue in the open.

"Wherever is fine with me, as long as you're willing to listen this time." Izuna mumbled but was still heard.

Once they were inside the office and the door was shut, Madara turned on his brother. "I thought I made myself clear last time. No spying on the other villages. You have any idea what kind of message that would send!"

"I would tell the others that you're playing it smart. Come now Madara, you don't actually believe that the other nations aren't preparing to move against us do you?" Izuna asked in disbelief.

"And if I am?"

"Then you're stupid. Think about it brother, we're the first village to actually be created full of war hardened clans with powerful Kekki Genki's. Making us the strongest village therefore a primary target."

Madara could understand where his brother was coming from, he truly did but that still didn't make his brothers actions ok.

"That still doesn't make what you do ok. The other villages could see it as acts of war.

"We're a village made up of clans, that were breed for that very thing. It's in our very blood to kill and wage war!"

"NO!" Madara yells his Dojutsu activating. "I won't except that! I'll never except it! I created this village as a fresh start for the people out there!" He shouts pointing at the window. "Our days of waging war ended when I killed our  
ended when I shook hands with Maya making our alliance official. It definitely ended when I married Mito. This village along with all the others, are testaments that people can put aside their differences and come together."

"Yea and look where those alliances have gotten us. We are own the strongest we've ever been because of you, but you refuse to use that power-"

"I am using that power Izuna. I'm using it to help change this world." Madara interrupts his brother.

"Pathetic. I looked up to you. Out of everyone in our clan, I thought you would be the greatest of them all. I can see now that you're just as weak compared to previous heads before you. I can see that this obviously isn't the place with me." Izuna said  
turning toward the door, only to stop when Madara said something else.

"If you think you can convince any members of our clan, think again. They'll never follow you."

"Then I'm not only betrayed by my brother, but my clan as well." Turning his head over his right shoulder Izuna activated his Sharingan and said his final words to his brother. "Goodbye Madara." And with that he left.

"Goodbye...Izuna." Madara never saw his brother again.

* * *

 _(Year Later)_  
 _  
_

A year has passed since Izuna's sudden departure from the village and things in the Elemental Nations changed. The left over clans that weren't apart of the four great nations, got together making up smaller villages. Shinobi's took on missions in a peaceful  
world and actually made it back hometo their families. And Madara was named the First Mizukage of Kirigakure.

The twenty five year old Kage was currently in his office, facing the number one enemy of all village leaders...paperwork.

It was the only thing he hated about being the leader, but it had to be done. The only things that kept him going was the fact his successor Maya would be stuck doing this, but more importantly it was his beautiful wife who he gets to go home to. The  
thought of Mito always brought a smile to his face, he had admitted to being in love with her since they were children, and how he always wanted to be with her but thought she would choose Hashirama over him. He was more than happy when she told him  
that she never felt any romantic feelings for him, and that he had won over her heart since being married. Mito was a month pregnant with their first child, who he hoped was girl always wanting to spoil his daughters if he had any. Only for Mito to  
dash his hopes claiming it was a boy do to mothers intuition. Either way he was excited to be a father.

Finishing the last of the reports, he lend back in his chair sighing looking out on the village.

Next month he would be traveling to the Land of Fire to meet with the Hokage of the Leaf Hashirama, in hopes forming an alliance because word got out that the cloud and stone village had one leaving only themselves, the leaf and sand.

Madara was excited to see his old friend again after so long. He couldn't wait to catch up with him and to congratulate him on his marriage to a member of the Hyuuga clan. Still he couldn't help but shake the feeling that something bad would happen.

Whatever it was, he would deal with it later. Right now he just wanted to get back home to his beautiful wife.

* * *

 **AN/: I'm speeding things up so I can get to Naruto's story.**

* * *

 _(Month Later)_  
 _  
_

"I still think it was a bad idea for you to come." Madara grumbles. They were in the land of fire in aneutral area decided by both parties, and apart of his guard was Maya and his pregnant wife. He tired to talk her out of it, but having a red hair wife  
who already has a temper only tends to worse, when you have a pregnant red hair hot tempered wife.

"I can take care of myself Madara. Besides I needed some fresh air."

"Can you guys break up the lovers quarrel. We have company." Maya inturrops.

"Madara it's so good to see you again old friend." He hears Hashirama greet him with a smile.

"Hashirama. It has indeed been a long time. I've missed you." Madara returns the smile embracing him like a brother,

Exchanging pleasantries for a bit, both groups got down to the talking about forming an alliance in case of war. Everything was going extremely well until they were interrupted by their escorts.

"Lord Hokage, Lord Mizukage. We've picked up a disturbance in the perimeter." Causing them the leaders to be alert.

"Maya no matter what happens. You are to protect my wife and child." He tells her getting a nod from her. Before sensing someone in front of them.

"Whoever is there, come out now!" Madara ordered.

"Now is that anyway to treat your little brother?" The stranger mocks being hurt.

"Izuna? Is that really you?" Madara asked shocked. Only to see his brother step out of the shadows wearing blue armor, Sharingan active and having a cruel smile on his face.

"It's good to see you Madara."


End file.
